package algorithm.poj;

/**
 * 
 * Poor Pformance!!!
 * 
 * @author wong.tong@gmail.com
 *
 */
@SuppressWarnings("unchecked")
public class BigInteger implements Comparable {
	
	public static final BigInteger ZERO	= new BigInteger("0");
	public static final BigInteger ONE 	= new BigInteger("1");
	public static final BigInteger TEN 	= new BigInteger("10");
	
	private int sign;
	private int[] digits;
	
	public BigInteger(String s) {
		
		this.str2num(s);
		this.digits = this.removePrefixZero(this.digits);
	}
	
	private BigInteger(int sign, int[] digits) {
		
		this.sign = sign;
		this.digits = digits;
	}

	private void str2num(String s) {

		this.sign = 1;
		if (s == null || s.trim().length() == 0) {
			this.digits = new int[0];
		} else {
			if (s.charAt(0) == '-') {
				this.sign = -1;
				s = s.substring(1);
			} else if (s.charAt(0) == '+') {
				this.sign = 1;
				s = s.substring(1);
			}
			
			char[] array = s.trim().toCharArray();
			this.digits = new int[array.length];
			for (int i = 0; i < digits.length; i ++) {
				digits[i] = array[digits.length-i-1]-'0';
			}
		}
	}
	
	/**
	 * r^n
	 * @param r
	 * @param n
	 * @return
	 */
	private int[] pow(int[] r, int n) {
		
		if (n == 0) {
			return new int[] {1};
		} else if (n == 1) {
			return r;
		} else {
			int[] ret = r;
			for (int i = 1; i < n; i ++) {
				ret = multiply(ret, r);
			}
			return ret;
		}
	}
	
	public BigInteger pow(int n) {
		
		int sign = (this.sign == -1 && n%2 != 0)?-1:1;
		return new BigInteger(sign, this.pow(this.digits, n));			
	}
	
	public BigInteger multiply(BigInteger t) {
		
		int sign = (t.sign != this.sign)?-1:1;
		return new BigInteger(sign, this.multiply(this.digits, t.digits));
	}
	
	public BigInteger add(BigInteger t) {
		
		if (t.sign == this.sign) {
			return new BigInteger(this.sign, add(this.digits, t.digits));
		} else {
			int comp = this.compare(this.digits, t.digits);
			if (comp >= 0) {
				return new BigInteger(this.sign, subtract(this.digits, t.digits));
			} else {
				return new BigInteger(t.sign, subtract(t.digits, this.digits));
			}
		}
	}

	private int[] multiply(int[] s, int[] t) {
		
		int[] r = new int[s.length + t.length];
		int c, m, d;
		
		c = 0;
		for (int i = 0; i < t.length; i ++) {
			c = 0;
			for (int j = 0; j < s.length; j ++) {
				m = t[i] * s[j];
				d = r[i+j] + m + c;
				r[i+j] = d%10;
				c = d/10;
			}
			if (c > 0) {
				r[i+s.length] += c;
			}
		}
		
		return removePrefixZero(r);
	}
	
	private int[] removePrefixZero(int[] r) {
		
		//remove prefix zero
		int idx = 0;
		for (idx = r.length-1; idx > -1; idx--) {
			if (r[idx] != 0) {
				break;
			}
		}
		if (idx == -1) {
			int[] rr = new int[1];
			rr[0] = 0;
			return rr;
		} else {
			int[] rr = new int[idx+1];
			for (int i = 0; i <= idx; i ++) {
				rr[i] = r[i];
			}
			return rr;
		}
	}
	
	private int[] add(int[] s, int[] t) {
		
		int len = Math.max(s.length, t.length)+1;
		int[] r = new int[len];
		int c = 0, d = 0;
		for (int i = 0; i < len; i ++) {
			d = c;
			d += (i < s.length)?s[i]:0;
			d += (i < t.length)?t[i]:0;
			r[i] = d%10;
			c = d/10;
		}
		return this.removePrefixZero(r);
	}
	
	/**
	 * s >= t
	 * @param s
	 * @param t
	 * @return
	 */
	private int[] subtract(int[] s, int[] t) {
		
		int[] r = new int[s.length];
		int c = 0;	//借位标志
		for (int i = 0; i < s.length; i ++) {
			int x = (i <= t.length-1)?t[i]:0;
			if (s[i] < c + x) {
				r[i] = s[i]+10-c-x; 
				c = 1;
			} else {
				r[i] = s[i]-c-x;
				c = 0;
			}
		}
		return this.removePrefixZero(r);
	}
	
	public BigInteger subtract(BigInteger t) {
		
		if (t.sign != this.sign) {
			return new BigInteger(this.sign, this.add(this.digits, t.digits));
		} else {
			int comp = this.compare(this.digits, t.digits);
			if (comp >= 0) {
				return new BigInteger(this.sign, subtract(this.digits, t.digits));
			} else {
				return new BigInteger(-t.sign, subtract(t.digits, this.digits));
			}
		}
	}
	
	private int[] divide(int[] s, int[] t) {
		
		if (s.length < t.length) {
			int[] r = new int[1];
			r[0] = 0;
			return r;
		} else {
			int[] r = new int[s.length-t.length+1];
			for (int i = r.length-1; i > -1; i --) {
				for (int j = 0; j < 10; j ++) {
					r[i] = j;
					int[] m = multiply(t, r);
					int comp = compare(m, s); 
					if (comp == 1) {
						r[i] = j-1;
						break;
					} else if (comp == -1) {
						continue;
					} else {
						return this.removePrefixZero(r);
					}
				}
			}
			return this.removePrefixZero(r);
		}
	}

	public BigInteger divide(BigInteger t) {
	
		if (compare(t.digits, new int[] {0}) == 0) {
			throw new RuntimeException("Divide Zero!");
		}
		if (t.sign == this.sign) {
			return new BigInteger(1, this.divide(this.digits, t.digits));
		} else {
			return new BigInteger(-1, this.divide(this.digits, t.digits));
		}
	}
	
	public BigInteger mod(BigInteger t) {
		
		BigInteger a = this.divide(t);
		return this.subtract(a.multiply(t));
	}

	@Override
	public String toString() {
		
		String s = "";
		if (this.sign == -1) s = "-";
		for (int i = this.digits.length-1; i > -1; i --) {
			s += this.digits[i];
		}
		return s;
	}

	public int compareTo(Object obj) {
		
		if (obj == null || !BigInteger.class.isAssignableFrom(obj.getClass())) {
			throw new RuntimeException("Wrong Type!");
		} else {
			BigInteger num = (BigInteger)obj;
			if (this.sign == num.sign) {
				return this.compare(this.digits, num.digits)*this.sign;
			} else {
				return this.sign;
			}
		}
	}

	private int compare(int[] x, int[] y) {
		
		if (x.length < y.length) {
			return -1;
		} else if (x.length > y.length) {
			return 1;
		} else {
			for (int i = x.length-1; i > -1; i --) {
				if (x[i] > y[i]) {
					return 1;
				} else if (x[i] < y[i]) {
					return -1;
				}
			}
			return 0;
		}
	}
	
	public boolean equals(Object obj) {
		
		if (obj == null || !BigInteger.class.isAssignableFrom(obj.getClass())) {
			return false;
		} else {
			BigInteger num = (BigInteger)obj;
			return this.compare(this.digits, num.digits) == 0;
		}
	}
}
